package com.gorkr.backtracking;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class M77Combinations {

    private List<List<Integer>> res = new LinkedList<>();
    private LinkedList trace = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {

        backTracking(n,k,1);

        return res;

    }

    /**
     *
     * @param n
     * @param k
     * @param start
     */
    private void backTracking(int n, int k, int start) {

        if(trace.size()>=k){
            res.add(new ArrayList<>(trace));
            return;
        }

        // 选择
        for (int i = start; i <=n; i++) {

            trace.add(i);

            backTracking(n,k,i+1);

            // 撤销选择
            trace.removeLast();
        }
    }

    @Test
    public void test(){
        System.out.println(combine(4, 2).toString());
    }


}
